package com.leetcode.partition1;

/**
 * @author `RKC`
 * @date 2021/8/6 11:21
 */
public class LC62不同路径 {

    public static int uniquePaths(int m, int n) {
//        return dynamicProgramming(m, n);
//        return dfs(m, n, 1, 1);
        return memoization(m, n, 1, 1, new int[m + 1][n + 1]);
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 2));
    }

    private static int memoization(int m, int n, int i, int j, int[][] memo) {
        if (i > m || j > n) return 0;
        if (i == m && j == n) return 1;
        if (memo[i][j] != 0) return memo[i][j];
        memo[i][j] = memoization(m, n, i + 1, j, memo) + memoization(m, n, i, j + 1, memo);
        return memo[i][j];
    }

    /**
     * 题目要求机器人只能向右或者向下走，因此可以抽象成一颗二叉树，而叶子结点就是终点
     * Time Limit Exceeded
     */
    private static int dfs(int m, int n, int i, int j) {
        //找到一种方法
        if (i == m && j == n) return 1;
        //边界判断
        if (i > m || j > n) return 0;
        return dfs(m, n, i + 1, j) + dfs(m, n, i, j + 1);
    }

    /**
     * 动态规划
     * 初始状态：dp[0][0]=1，因为只能向右或向下走，因此dp[0][0...n]=0 dp[0...m][n]=1
     * 过程：dp[i][j]=dp[i-1][j]+dp[i][j-1]
     * 终止状态：i=m-1且j=n-1
     */
    private static int dynamicProgramming(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}
